In a concurrent processing environment multiple sets of instructions, herein referred to as tasks, may be executed simultaneously. The act of starting a new task is referred to as spawning. The task which spawns the new task is called the parent, while the task being spawned is the child. A task is referred to as being alive if it is either still executing or still capable of being scheduled to execute. A task is referred to as dead if it has finished executing.
Parallel computer programs are fundamentally more difficult to validate, test, and debug than sequential computer programs. While typical programs can exhibit traditional “sequential” errors, such as those caused by incorrect syntax, program logic, control flow, or rounding or truncation of numerical results, parallel programs can exhibit additional types of errors. Parallel programming errors can result from parallelizing a sequential program, wherein constraints on the ordering of operations in the original sequential program are relaxed in order to exploit parallelism, which results in unintended indeterminacy. In addition, errors can result from the incorrect application or use of parallel programming constructs; many of these errors are difficult or impossible to detect statically, especially without employing interprocedural analysis.
Currently, it remains difficult to detect errors caused by the incorrect use of parallel programming constructs or with respect to the general problem of parallel program validation. For example, current race detection schemes employ either static, post-mortem, or on-the-fly analysis methods. Static methods suffer the disadvantage of being overly conservative since they do not resolve references that must be analyzed at runtime. Post-mortem methods require the production and storage of extremely large amounts of data in order to provide complete, accurate race analysis. And, reducing the amount of data results in correspondingly less accurate analysis. On-the-fly race analysis helps eliminate the requirement of storing large amounts of post-mortem analysis data, without sacrificing the accuracy of dynamic analysis techniques.
Most race detection schemes, however, require parallel execution of the program being analyzed. These methods typically require a particular parallel machine on which to execute the parallel program, and thus cannot analyze parallel programs with severe errors that prevent parallel execution or cause abnormal termination. Dynamic dependence analysis methods detect data races that could potentially occur during execution of a parallel program via on-the-fly analysis of the corresponding sequential program. These methods do not require parallel execution, and they isolate the analysis from particular timings or interleavings of events, scheduling methods, or numbers of processors or threads used. However, dynamic dependence analysis schemes do not detect errors arising from incorrect parallel programming construct use, and do not fully support a complete parallel programming language or dialect.
Most race detection schemes, even those employing the so-called sequential traces, are limited in several ways. First, they suffer all the disadvantages of dynamic methods that require parallel execution: the schemes are inherently less portable, and they cannot analyze parallel programs with catastrophic errors. Second, many of these schemes assume simplified parallel programming models, and most are not based on realistic, complete parallel programming languages or dialects. While these schemes address the issue of language generality, they still suffer the disadvantage of requiring parallel execution, which limits the classes of errors that can be analyzed, and the portability and applicability of the methods.
Other relative debugging techniques also suffer the disadvantages of most of the aforementioned schemes (i.e., requiring parallel execution, analyzing one particular parallel execution). Thus, some degree of parallel execution is still required. Some techniques have been developed which attempt to analyze a concurrent processing environment using sequential execution (i.e., using just one thread and projecting all of the other threads of execution of the program being debugged onto this one thread); however they tend to be very restrictive and inefficient.
Systems and methods are needed that can overcome the above-noted shortcomings.
Features, elements, and aspects of the invention that are referenced by the same numerals in different figures represent the same, equivalent, or similar features, elements, or aspects, in accordance with one or more embodiments.